import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/21 11:30
 * @description 广度优先遍历，将所有入度为0的节点，加入列表，同时删除（u,v)中所有与u开头的边，u相邻节点入度减1，如果变为0，那么加入队列中
 */
public class Solution2 {
    public static void main(String[] args) {

    }

    /**
     * 存储有向图
     */
    List<Integer>[] edges;
    /**
     * 存储每个节点的入度
     */
    int[] in;
    /**
     * 存储答案
     */
    int[] result;
    /**
     * 答案下标
     */
    int index;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        edges = new List[numCourses];
        for (int i = 0; i < numCourses; ++i) {
            edges[i] = new ArrayList<Integer>();
        }
        in = new int[numCourses];
        result = new int[numCourses];
        index = 0;
        for (int[] info : prerequisites) {
            edges[info[1]].add(info[0]);
            ++in[info[0]];
        }

        Queue<Integer> queue = new LinkedList<Integer>();
        // 将所有入度为 0 的节点放入队列中
        for (int i = 0; i < numCourses; ++i) {
            if (in[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            // 从队首取出一个节点
            int u = queue.poll();
            // 放入答案中
            result[index++] = u;
            for (int v: edges[u]) {
                --in[v];
                // 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了
                if (in[v] == 0) {
                    queue.offer(v);
                }
            }
        }
        if (index != numCourses) {
            return new int[0];
        }
        return result;
    }
}
